Integrated circuits (ICs) can be implemented to perform a variety of functions. Some ICs can be programmed to perform specified functions. One example of an IC that can be programmed is a field programmable gate array (FPGA). An FPGA typically includes an array of programmable tiles. These programmable tiles can include, for example, input/output blocks (IOBs), configurable logic blocks (CLBs), dedicated random access memory blocks (BRAM), multipliers, digital signal processing blocks (DSPs), processors, clock managers, delay lock loops (DLLs), and so forth.
Each programmable tile typically includes both programmable interconnect circuitry and programmable logic circuitry. The programmable interconnect circuitry typically includes a large number of interconnect lines of varying lengths interconnected by programmable interconnect points (PIPs). The programmable logic circuitry implements the logic of a user design using programmable elements that can include, for example, function generators, registers, arithmetic logic, and so forth.
The programmable interconnect circuitry and programmable logic circuitry are typically programmed by loading a stream of configuration data into internal configuration memory cells that define how the programmable elements are configured. The configuration data can be read from memory (e.g., from an external PROM) or written into the FPGA by an external device. The collective states of the individual memory cells then determine the function of the FPGA.
Another type of programmable IC is the complex programmable logic device, or CPLD. A CPLD includes two or more “function blocks” connected together and to input/output (I/O) resources by an interconnect switch matrix. Each function block of the CPLD includes a two-level AND/OR structure similar to those used in programmable logic arrays (PLAs) and programmable array logic (PAL) devices. In CPLDs, configuration data is typically stored on-chip in non-volatile memory. In some CPLDs, configuration data is stored on-chip in non-volatile memory, then downloaded to volatile memory as part of an initial configuration (programming) sequence.
For all of these programmable ICs, the functionality of the device is controlled by data bits provided to the device for that purpose. The data bits can be stored in volatile memory (e.g., static memory cells, as in FPGAs and some CPLDs), in non-volatile memory (e.g., FLASH memory, as in some CPLDs), or in any other type of memory cell.
Other programmable ICs are programmed by applying a processing layer, such as a metal layer, that programmably interconnects the various elements on the device. These programmable ICs are known as mask programmable devices. Programmable ICs can also be implemented in other ways, e.g., using fuse or antifuse technology. The phrase “programmable IC” can include, but is not limited to these devices and further can encompass devices that are only partially programmable. For example, one type of programmable IC includes a combination of hard-coded transistor logic and a programmable switch fabric that programmably interconnects the hard-coded transistor logic.
To implement a circuit design within an IC, e.g., a programmable IC, the various hardware units available within the IC are configured to perform a function of a component, e.g., implement the component, in the circuit design. Implementing the circuit design within the IC typically requires a plurality of processing steps. One of the processing steps is called partitioning. Partitioning refers to a process in which components of a circuit design are grouped into “partitions.” Each of the partitions is assigned to a particular region, e.g., a physical area, of the IC. The components assigned to a partition are implemented using the hardware units available within the region to which the partition is assigned.
The electronic design automation (EDA) tools that implement the partitioning process are referred to as “partitioners.” Partitioners suffer from several disadvantages that render the tools less effective for use with modern circuit designs and modern ICs. One disadvantage of many partitioners is the inability to partition a circuit design across more than two different regions. Many partitioners, for example, can bisect a circuit design, but are not scalable to address situations in which an IC is to be divided into three or more partitions or regions.
Another disadvantage of many partitioners is the inability to contend with more than one type of component and corresponding hardware unit. Such partitioners can treat the circuit design as if the entire circuit design includes only a single type of component. Partitioners that recognize only a single component type are unable to effectively partition a circuit design that includes multiple types of components that is to be implemented in more complex ICs of the varieties described herein.